import java.util.Deque;
import java.util.LinkedList;

public class MyStack {

    private Deque<Integer> dq1;
    private Deque<Integer> dq2;

    public MyStack(){
        dq1 = new LinkedList<>();
        dq2 = new LinkedList<>();
    }

    public void push(int val){
       if(!dq1.isEmpty()){
           dq1.offer(val);
       }else if(!dq2.isEmpty()){
           dq2.offer(val);
       }else{
           dq1.offer(val);
       }
    }
    public int pop() {
        if(dq1.isEmpty() && dq2.isEmpty()) return -1;

        if(!dq1.isEmpty()){
            int size = dq1.size();
            while(size - 1 != 0){
                dq2.offer(dq1.poll());
                size--;
            }
            return dq1.poll();
        }else{
            int size = dq2.size();
            while(size - 1 != 0){
                dq1.offer(dq2.poll());
                size--;
            }
            return dq2.poll();
        }
     }

      public int top() {
          if(dq1.isEmpty() && dq2.isEmpty()) return -1;

          if(!dq1.isEmpty()){
              int size = dq1.size();
              while(size - 1 != 0){
                  dq2.offer(dq1.poll());
                  size--;
              }
              int val = dq1.poll();
              dq2.offer(val);
              return val;
          }else{
              int size = dq2.size();
              while(size - 1 != 0){
                  dq1.offer(dq2.poll());
                  size--;
              }
              int val = dq2.poll();
              dq1.offer(val);
              return val;
          }
      }

      public boolean empty() {
         if(dq1.isEmpty()&& dq2.isEmpty()) {
             return true;
         }
         return false;
      }

}
